#pragma once
#include <stack>

using namespace std;

namespace checkBrackets
{
	class Solution {
	public:
		bool isValid(string s) {
			stack<char> stk;
			for (size_t i = 0; i < s.length(); i++)
			{
				char c = s[i];
				if (c == '(' || c == '[' || c == '{')
				{
					stk.push(c);
				}
				else if ( ( c == ')' && !stk.empty() && stk.top() == '(')
						|| ( c == ']' && !stk.empty() && stk.top() == '[')
						|| ( c == '}' && !stk.empty() && stk.top() == '{')
				)
				{
					stk.pop();
				}
				else
				{
					return false;
				}
			}

			return stk.empty();
		}
	};
}